The present invention relates to a Viterbi decoding method and Viterbi decoding circuit suitable for decoding a convolutional code in which the initial and final states of the coder are unknown, but are identical.
A convolutional code of this type is employed in, for example, the fast associated control channel (FACCH) of the North American time-division multiple-access (TDMA) digital cellular telephone system. The convolutional coder has a finite number of states, among which transitions occur in response to the data to be coded. The Viterbi decoding algorithm is a well-known maximum-likelihood algorithm that constructs hypothetical paths among these states in the coder, keeping track of one most likely path terminating on each state. When the paths reach a certain length, the most likely path of all is selected and retraced to obtain the decoded data.
If the decoded data turn out to be incorrect, one possible cause is that the decoder selected the path terminating on the wrong state. One possible solution is accordingly to select different states and trace a path from each one in turn, until correct data are obtained. The paths should be traced in decreasing order of likelihood. Unfortunately, many paths tend to have similar likelihood values, and there is no guarantee that the correct path will have one of the highest likelihood values. It will often be necessary to test a large number of paths before finding the correct one, so this solution can be quite time-consuming
Another possible solution is to provide extra hardware, so that the paths from different states can all be traced in parallel. The necessary amount of hardware is not small, however. The FACCH coder, for example, has thirty-two states, so performing all traces in parallel would multiply the hardware requirements by a factor of thirty-two.
A further problem is that it is difficult to tell whether a decoding error is due to selection of the wrong path, or some other reason. In the latter case, correct data will not be obtained from any trace, and the repeated traces will all be in vain.
This problem would not occur if the initial and final states were fixed, but the restriction to fixed initial and final states would reduce the amount of information that could be coded. Conversely, unfixed initial and final states permit more information to be coded within a given number of bits, but the decoding error rate is increased, because the decoder does not know the initial and final states in advance.